package LearnAlgorithm.d_标准查找算法and标准排序算法;

import java.util.ArrayList;

public class b9b基数排序 {
	public static ArrayList<Integer>[] bucket = new ArrayList[10];//定义用在自然数上一定足够的桶
	static {//为每个桶进行初始化
		for (int i = 0; i < bucket.length; i++) {
			bucket[i] = new ArrayList<Integer>();
		}
	}
	public static void main(String[] args) {
		int[] arr = new int[] {9,8,6,5,4,7,1,10,15,14,16};
		long before = System.currentTimeMillis();
		radixSort(arr);
		util.Util.duration(before);
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}
	
	/**
	 * 基数排序
	 * 不能处理负数
	 * 处理自然数非常有效
	 * O(NlogN)
	 * @param arr
	 */
	public static void radixSort(int[] arr) {
		int numCurrent = 1;//定义代表第几位(数值=1)，十位(数值=2)，百位(数值=3).....
		int max = maxFind(arr);//定义数组最大值
		int maxNums = 1;//定义最大值的数值的最大位数
		while (max / 10 != 0) {
			maxNums++;
			max /= 10;
		}
		while (numCurrent <= maxNums) {
			sort(arr,numCurrent++);//根据第二个参数入桶出桶
		}
	}
	
	/**
	 * 基数排序---核心处理
	 * 将数组arr按第(numCurrent)位进行分配和收集
	 * @param arr
	 * @param numCurrent
	 */
	public static void sort(int[] arr, int numCurrent) {
		int current = 0;
		//全部入桶
		for (int i = 0; i < arr.length; i++) {
			putInBucket(arr[i], getDigitOn(arr[i], numCurrent));
		}
		//全部出桶；将每个桶中的元素依次压入原数组arr
		for (int i = 0; i < bucket.length; i++) {
			for (Integer m : bucket[i]) {
				arr[current++] = m;//自动装箱拆箱
			}
		}
		clearAll();
	}
	
	/**
	 * 入桶方法
	 * @param data
	 * @param digitOn
	 */
	public static void putInBucket(int data, int digitOn) {
		switch (digitOn) {
		case 0:
			bucket[0].add(data);
			break;
		case 1:
			bucket[1].add(data);
			break;
		case 2:
			bucket[2].add(data);
			break;
		case 3:
			bucket[3].add(data);
			break;
		case 4:
			bucket[4].add(data);
			break;
		case 5:
			bucket[5].add(data);
			break;
		case 6:
			bucket[6].add(data);
			break;
		case 7:
			bucket[7].add(data);
			break;
		case 8:
			bucket[8].add(data);
			break;
		case 9:
			bucket[9].add(data);
			break;
		default:
			break;
		}
	}
	
	/**
	 * 获取数字num在第(numCurrent)位上的数值 
	 * 从个位开始计数
	 * 个位：src/1 % 10
	 * 十位：src/10 %10 
	 * 百位：src/100 %10
	 * @param num
	 * @param numCurrent
	 * @return
	 */
	public static int getDigitOn(int num, int numCurrent) {
		return num / (int) (Math.pow(10, numCurrent - 1)) % 10;//pow(x,y)	x的y次方
	}
	
	/**
	 * 清除集合数组中的所有集合的元素
	 */
	public static void clearAll() {
		for (ArrayList<Integer> arrayList : bucket) {
			arrayList.clear();
		}
	}
	
	public static int maxFind(int[] arr) {
		int max = arr[0];
		for (int i = 0; i < arr.length; i++) {
			if (max <= arr[i]) {
				max = arr[i];
			}
		}
		return max;
	}
}
